1. Field of the Invention
The invention relates to the field of handling NP-complete problems. In particular the invention relates to the provision of a method and system to provide reasonable solutions to NP-complete problems in a practical manner.
2. Description of the Related Technology
Many mathematical problems are not subject to an optimal solution by either an algorithmic approach or an heuristic approach, (e.g. trial and error methods). On area in which this is a particular problem is with network logic diagrams and other non-deterministic polynomial time-complete (NP-complete) problems. These types of problems are encountered in many fields such as graph theory, network design, sets and partitions, data storage and retrieval, sequencing and scheduling, mathematical programming, algebra and number theory, games and puzzles, logic, automation, language theory, program optimization, as well as other areas.
In such cases, the only practical means of determining a reasonably good answer is to solve the problem using one or more of a potentially infinite number of algorithms, repeat this process a finite number of times and compare the results to choose a best answer. Alternatively, heuristic methods can be employed. Both approaches are time-consuming and tedious for implementation by, for example, non-technical personnel.
There are a variety of alternative approaches to the solution of NP-complete problems. For example, U.S. Pat. No. 5,913,201 (Kocur) uses a combination of linear programming and a heuristic to address an NP-complete problem in the area of scheduling.
U.S. Pat. No. 6,606,529 provides a method for finding a solution to a multi-task scheduling problem by applying artificial intelligence to partition or fragment the problem into a set of mathematically independent scheduling problems, selecting one of a plurality of algorithms which will provide an optimal solution in minimal time to each sub-problem, repeating the process for each sub-problem and then combining the solutions to provide an optimal solution. This method, however, has the drawback that each type of scheduling sub-problem must be anticipated and a suitable algorithm for solving it must be provided.
U.S. Pat. No. 6,636,840 provides a method for solving NP-complete problems. The system is configured to solve the minimal Hamiltonian cycle of a primary network comprised either of edges having non-binary or binary valued weights. The solutions are arrived at by changing the weighting of the edges in the system and repeating the calculations until a predetermined condition is satisfied.
In the field of project planning and management, NP-complete problems are frequently encountered. The Critical Path Method (CPM) is one of several related techniques that employ level for project planning. CPM is used to analyze projects that involve a number of individual activities. It analyzes what activities have the least amount of scheduling flexibility (i.e., are the most mission-critical) and then predicts the duration of the project based on the activities that fall along the so-called “critical path.” Activities that are part of the critical path cannot be delayed without delaying the finish time for the entire project. The CPM may involve graphically diagramming how each activity is related to the others. An example of this diagramming can be seen in FIG. 1. In FIG. 1 each letter represents an activity that needs to be completed and each number represents a node that indicates when that activity needs to be completed in relation to the other activities. Time estimates are then given to each of the activities in order to estimate how long it will take to complete the activity. The longest path in the diagram is the critical path and provides an estimate of the time needed to complete a project. It also illustrates which activities are not critical for the completion of a project in a timely fashion.
Leveling, defined as the scheduling of activities of a logic network restricted to finite resources, is one example of a NP-Complete problem. For a network of n activities, there are possible n−1 choices of preferred sequence priority of performances leading to the shortest time required for completion of all activities in the logic network. Increasing or decreasing the durations of individual activities may have an impact to this process that is counter-intuitive, such as a decrease of one day duration for each activity yielding a longer total project completion. This is exemplified in FIGS. 1A-1C of the present application.
If the logic network is scheduled (by a CPM algorithm) prior to leveling, priority may be assigned by one of the calculated attributes of the scheduling algorithm rather than by a random choice of the n−1 possibilities. The number of these calculated attributes (as well as input attributes) is far fewer than the number of activities in the typical project. (Calculated attributes may include early start, early finish, late start, late finish, total float, free float, independent float and possibly others. Input attributes may include duration, number of limited resources, number of predecessors, number of successors and possibly others.)
In most cases where scheduling is performed prior to leveling, the leveling routine will yield an earlier completion time. However, the choice of which attribute(s) may be the basis of priority, and order thereof where more than one attribute is chosen, can yield dramatically differing results. For example, where many limited resources are being allocated amongst activities, the difference in which priority list is used can result in a total project duration double that of the optimum or shortest project duration.
The “fix” often suggested by software vendors is to level the project based upon the manual development of a priority list, or priority scheme of choice of order of attributes, sequentially repeating the process for several other priority lists, manually determining which priority list yields the best results and then rekeying the priority list that provided that best result. For all but those projects where every activity is performed exactly as planned, this process must be repeated for each review period. The review period will typically range from one week to one month in the construction industry. The review period will typically range from fifteen minutes to one shift in the manufacturing sector. Other industries will have similar typical ranges of review periods. Although there may be several hundred to thousands of possible priority list schemes, the software vendors will typically recommend the use of a select few priority lists as the basis for the process noted above.
Computer programs have been developed to help facilitate the planning of projects. Typically after entering in the necessary information to create a plan for the project, certain rule sets are adjusted and entered into the computer program using trial and error, in order to determine the effect these rule sets on the overall project. This trial and error method wastes valuable time in providing with a project plan. As a practical result, an exceedingly few licensees of CPM scheduling software with leveling capabilities actually use this function, instead usually manually leveling their schedules by a “seat of the pants” allocation of resources that may, or may not, approach an optimal solution.
Therefore, there exists a need for providing an efficient method for applying a number of rule sets to a proposed list of activities and determining which rule set is optimal, given the goals of the project.